package com.longge;

import java.util.*;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-04-26 01:26
 */
public class MergeAccounts {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        HashMap<String, Integer> emailIndex = new HashMap<>();
        HashMap<String, String> emailName = new HashMap<>();
        int count = 0;
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                if (!emailIndex.containsKey(email)) {
                    emailIndex.put(email, count++);
                    emailName.put(email, name);
                }
            }
        }
        UF uf = new UF(count);
        for (List<String> account : accounts) {
            String firstEmail = account.get(1);
            for (int i = 2; i < account.size(); i++) {
                String email = account.get(i);
                uf.union(emailIndex.get(firstEmail),emailIndex.get(email));
            }
        }
        HashMap<Integer, List<String>> indexEmail = new HashMap<>();
        for (String email : emailIndex.keySet()) {
            int index = uf.findRoot(emailIndex.get(email));
            List<String> emails = indexEmail.getOrDefault(index, new ArrayList<String>());
            emails.add(email);
            indexEmail.put(index,emails);
        }

        List<List<String>> res = new ArrayList<>();
        for (Integer index : indexEmail.keySet()) {
            ArrayList<String> col = new ArrayList<>();
            List<String> emails = indexEmail.get(index);
            emails.sort(String::compareTo);
            String email = emails.get(0);
            String name = emailName.get(email);
            col.add(name);
            col.addAll(emails);
            res.add(col);
        }
        return res;

    }
}
